The present invention relates to a vector processor, and more specifically to a vector processor suited for processing symbols, such as by sorting the symbols.
So far, an apparatus has been known which consists of specially designed hardware for sorting data sequences at high speeds, relying upon vector processing as disclosed in Japanese Patent Laid-Open No. 134973/1985 (or corresponding U.S. patent application Ser. No. 685616 or corresponding EP 84 116094.8). This apparatus makes it possible to sort mergings in the form of vectors that could not hitherto have been treated in the form of vectors.
According to the above prior art, however, no attention has been given to cases where data sequences that are to be sorted are biased, e.g., where input data sequences have almost all been sorted already. This problem will now be described briefly with reference to drawings.
FIG. 10 is a diagram which schematically illustrates a sorting method using a vector processor according to the conventional art. When the input vector elements to be sorted consist of 2, 5, 7, 4, 1, 6, 8 and 3 according to this method, the vector elements are divided at the center into two vectors, i.e., X=(2, 5, 7, 4) and Y=(1, 6, 8, 3). Next, based on a prerequisite that the data are arranged in a random fashion in the vectors X and Y, the length of ascending order elements in each of the vectors is designated to be 1 to serve as a parameter at the time of executing the merge sorting instruction, and the data are merged one by one from the start of the vectors X and Y. The merging stands for a processing in which the elements of X and Y are compared and the smaller one (or the larger one) is produced. As a result, vectors 1, 2, 5, 6, 7, 8, 3 and 4 are produced in which successive pairs of elements have been sorted. Therefore, the vectors are divided again into a vector X=(1, 2, 5, 6) and a vector Y=(7, 8, 3, 4). The merge sorting instruction now designates that there are ascending order elements having a length 2 in each of the vectors, and then the successive pairs of elements are merged. As a result, vectors 1, 2, 7, 8, 3, 4, 5 and 6 are produced in which successive four elements are sorted. The vectors are divided again into X=(1, 2, 7, 8) and Y=(3, 4, 5, 6). This time, the elements are merged with the length of ascending order elements as 4, and the sorting of the whole elements is completed.
According to this system, it is allowable to designate only elements having a predetermined length as ascending order elements in the vectors, but it is not allowable to process vectors that consist of elements having varying lengths. That is, the length of the ascending order elements is doubled for each merging, i.e., the length increases to 1, 2, 4, -- for each merging. Therefore, if the length of the input vector is N, the merging must be carried out log.sub.2 N times. In this case, the merging must be carried out log.sub.2 8=3 times. This system is based on the presumption that the input vectors are arranged in a random fashion. In practically inputting the data, however, the data are biased in many cases. For instance, the data may be arranged nearly in ascending order from the first. This system, however, is not capable of utilizing the nature of such data elements.
A known method adapted to the scalar processor consists of utilizing the properties that exist in the data elements to increase the efficiency (e.g., see Knuth, E. E.: "The Art of Computer Programming Vol. 3, Sorting and Searching", Addison-Wesley (1973)).
By merging ascending order data elements having varying lengths or descending order data elements having varying lengths in the input data elements, it is possible to perform the sorting with a reduced number of mergings compared with merging by the conventional scalar processor.
The above-mentioned literature, however, does not disclose how the above method can be adapted to a vector processor.